/*************************************************************************
 * File Name:    Maximal_Rectangle.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 21 Sep 2013 04:53:59 PM CST
 * 
 * Description:  
 *
 | ------------------------------------------------------------------------
 | Maximal Rectangle
 |
 | Given a 2D binary matrix filled with 0's and 1's, find the largest Rectangle
 | containing all ones and return its area.
 |
 | ------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

class Solution {
public:
    int maximalRectangle_2(vector<vector<char> > &matrix)
    {
        if (matrix.size() == 0) return 0;
        int row = matrix.size();
        int col = matrix[0].size();
        
        vector<vector<int> > dp(row, vector<int>(col + 1, 0));
        for (int i = 0; i < row; ++i) {
            for (int j = 1; j <= col; ++j) {
                if (matrix[i][j - 1] == '1') dp[i][j] = dp[i][j - 1] + 1;
                else dp[i][j] = 0;
            }
        }
        
        int min_len, ans = 0;
        for (int i = 1; i <= col; ++i) {
            for (int j = 0; j < row; ++j) {
                min_len = dp[j][i];
                for (int k = j; k < row; ++k) {
                    min_len = min(min_len, dp[k][i]);
                    if (ans < min_len * (k - j + 1)) {
                        ans = min_len * (k - j + 1);
                    }
                }
            }
        }
        return ans;
    }

    int maximalRectangle(vector<vector<char> > &matrix)
    {
        if (matrix.size() == 0) return 0;
        int row = matrix.size();
        int col = matrix[0].size();
        vector<int> height(col, 0);
        
        int t, ans = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '1') ++height[j];
                else height[j] = 0;
            }
            t = calc_max_area(height);
            ans = max(t, ans);
        }
        return ans;
    }
    
    int calc_max_area(const vector<int> &height)
    {
        vector<int> width(height.size(), 0);
        
        stack<int> s;
        for (size_t i = 0; i < height.size(); ++i) {
            while (!s.empty() && height[s.top()] >= height[i]) {
                s.pop();
            }
            if (s.empty()) width[i] = i + 1;
            else width[i] = i - s.top();
            
            s.push(i);
        }
        while (!s.empty()) s.pop();
        
        for (size_t i = height.size(); i > 0; --i) {
            while (!s.empty() && height[s.top()] >= height[i - 1]) {
                s.pop();
            }
            if (s.empty()) width[i - 1] += height.size() - i;
            else width[i - 1] += s.top() - i;
            
            s.push(i - 1);
        }
        
        int ret = 0;
        for (size_t i = 0; i < height.size(); ++i) {
            ret = max(ret, width[i] * height[i]);
        }
        return ret;
    }
};

int
main(int argc, char *argv[])
{
    vector<vector<char> > matrix;

    //matrix.push_back(vector<char>(3, '0'));
    //matrix.push_back(vector<char>(3, '0'));
    //matrix.push_back(vector<char>(3, '1'));

    //matrix[0][0] = '0';
    //matrix[1][1] = '0';

    matrix.push_back(vector<char>(2, '0'));
    matrix[0][0] = '1';

    Solution sol;

    cout << sol.maximalRectangle(matrix) << endl;

    return 0;
}
